package com.maishi.programmer.jainzhioffer;

import java.util.ArrayList;

/**
 * Created by brossdong on 2018/4/15.
 * 和为S的连续正数序列
 */
public class TestProblem57_1 {

    /**
     * 输出所有和为S的连续正数序列。
     * 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {

        /**
         * 初始化small=1，big=2;
         * small到big序列和小于sum，big++;大于sum，small++;
         * 当small增加到(1+sum)/2是停
         */
        ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
        if (sum <= 1) return lists;
        int small = 1;
        int big = 2;
        while (small != (1 + sum)/2) {
            int curSum = sumOfList(small,big);
            if (curSum == sum) {
                ArrayList<Integer> list = new ArrayList<Integer>();
                for (int i = small;i <= big;i++) {
                    list.add(i);
                }
                lists.add(list);
                small++;
                big++;
            } else if (curSum < sum) {
                big++;
            } else {
                small++;
            }
        }
        return lists;
    }

    //计算当前序列的和
    public int sumOfList (int head,int leap) {
        int sum = head;
        for (int i = head + 1;i <= leap;i++) {
            sum += i;
        }
        return sum;
    }

    public static void main(String[] args) {
        TestProblem57_1 test = new TestProblem57_1();
        ArrayList<ArrayList<Integer>> arrayLists = test.FindContinuousSequence(100);
        System.out.println(arrayLists);
    }


}
